{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Resourcing: Product Mix of Aluminium Windows" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction ##\n", "In this notebook we will use: \n", "\n", "- The Python open source Linear Programming library [PuLP](http://pythonhosted.org/PuLP/) to model and solve linear problems\n", "- The Python open source data analysis library [Pandas] (https://pandas.pydata.org/) to show the results\n", "- The IPython model display [Display] (https://ipython.org/ipython-doc/3/api/generated/IPython.display.html) to format the output \n", "- The Python numpy library [Numpy] (http://www.numpy.org/) to perform basic operations. \n", "\n", "We wil learn how to model problems in a way that scales to hundreds or thousands of variables and how to get all valuable information from the results generated by PuLP.\n", "\n", "Warning, you cannot test this notebook unless you install Gurobi in your environment." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Definition\n", "\n", "Weyland Corp is a British firm that manufactures solar panel cells. This firm supplies three different types of cell called: fast, normal and ultra. There are three operations involved in the manufacturing process. The following table describes the hours/month required to manufacture each model: \n", "\n", "**Table 1:** hours/month requirements\n", "\n", "| Operation | Fast (hours/cell) | Normal (hours/cell) | Ultra (hours/cell) | \n", "|-----------|-------------------|---------------------|--------------------|\n", "| 1 | 1 | 3 | 2 |\n", "| 2 | 2 | 0 | 3 |\n", "| 3 | 1 | 4 | 0 |\n", "\n", "And the following table describes the total hours available for each operation:\n", "\n", "**Table 2:** Total hours/month available\n", "\n", "| Operation | Hours/Month |\n", "|-----------|-------------|\n", "| 1 | 400 |\n", "| 2 | 600 |\n", "| 3 | 600 |\n", "\n", "The profit per each model is specified in the following table:\n", "**Table 3:** Unit of profit per model\n", "\n", "| Model | Profit/Unit |\n", "|--------|-------------|\n", "| Fast | 30 |\n", "| Normal | 20 |\n", "| Ultra | 40 |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Model\n", "### Decision variables\n", "The decision variables are: \n", "\n", "$x_1:$Units of Fast cells / month\n", "\n", "$x_2:$Units of Normal cells / month\n", "\n", "$x_3:$Units of Ultra cells / month\n", "\n", "### Objective Function\n", "The objective function is:\n", "\n", "$\\max z=30x_1+20x_2+40x_3$\n", "\n", "### Constraints\n", "Subject to the following constraints:\n", "\n", "$x_1+3x_2+2x_3 \\leq 400$\n", "\n", "$2x_1+0x_2+3x_3 \\leq 600$\n", "\n", "$x_1+4x_2+0x_3 \\leq 600$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Solution with Pulp\n", "Let us solve the problem with pulp. We start by importing PULP and instantiating the problem:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [], "source": [ "import pandas as pd\n", "import numpy as np\n", "from IPython.display import display, Markdown\n", "import pulp" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "c:\\python38\\lib\\site-packages\\pulp\\pulp.py:1199: UserWarning: Spaces are not permitted in the name. Converted to '_'\n", " warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n" ] } ], "source": [ "# Instantiate our problem class\n", "model = pulp.LpProblem(\"Maximising profits for Weyland Corp\", pulp.LpMaximize)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this problem, we have three decision variables. We could name them individually like in the first example, but this does not scale (imagine we had hundreds). Instead, we will use lists and tuple lists which can be really useful to minimise the problem configuration. \n", "\n", "First we create the lists:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [], "source": [ "# Construct our decision variable lists\n", "cell_types = ['fast', 'normal', 'ultra']" ] }, { "cell_type": "markdown", "metadata": {}, "source": "The decision variables have the same characteristics (lower bound of 0, continuous variables). We can use the LpVariable object's dict functionality to create the variables from the tuples. The good thing about tuples is that we could add more dimensions (e.g. cell categories) and still create all decision variables in one line of code." }, { "cell_type": "code", "execution_count": 13, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [], "source": [ "cell_units = pulp.LpVariable.dicts(\"cells\",\n", " (i for i in cell_types),\n", " lowBound=0,\n", " cat='Continuous')" ] }, { "cell_type": "markdown", "metadata": {}, "source": "PuLP provides an lpSum vector calculation for the sum of a list of linear expressions. Although we only have 6 decision variables, we will use lpSum to construct the expression using this feature, again for the sake of scalability.\n" }, { "cell_type": "code", "execution_count": 14, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [], "source": [ "# Technological Coefficients:\n", "unit_profits = [30, 20, 40]\n", "# Objective Function\n", "\n", "model += (\n", " pulp.lpSum([\n", " unit_profits[i] * cell_units[cell_types[i]]\n", " for i in range(len(cell_types))])\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": "Now we add the constraints using the tuples to identify the coefficients" }, { "cell_type": "code", "execution_count": 15, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [], "source": [ "# Operations \n", "operations = [\"Operation 1\", \"Operation 2\", \"Operation 3\"]\n", "# Constraints\n", "A=[[1, 3, 2], #Coefficients of the first constraint\n", " [2, 0, 3], #Coefficients of the second constraint\n", " [1, 4, 0]] #Coefficients of the third constraint\n", "\n", "# Capacities\n", "b = [400, 600, 600]\n", " #Iterate matrix raws\n", "for i in range(len(A)):\n", " model += pulp.lpSum([\n", " A[i][j] * cell_units[cell_types[j]] \n", " for j in range(len(cell_types))]) <= b[i] , operations[i] \n", "#note that in this case all constraints are of type less or equal" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [ { "data": { "text/plain": [ "'Optimal'" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Solve our problem\n", "model.solve(solver=pulp.GUROBI(msg = 0))\n", "\n", "pulp.LpStatus[model.status]" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "pycharm": { "is_executing": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Total profit is 9666.67 €\n", "The following table shows the decision variables: \n", "| | Variables | Solution (GRB) | Reduced cost (GRB) | Objective Coefficient (GRB) | Objective Lower bound (GRB) | Objective Upper bound (GRB) |\n", "|:-------|:-------------|-----------------:|---------------------:|------------------------------:|------------------------------:|------------------------------:|\n", "| fast | cells_fast | 300 | 0 | 30 | 24.44 | inf |\n", "| normal | cells_normal | 33.33 | 0 | 20 | -0 | 90 |\n", "| ultra | cells_ultra | 0 | -8.33 | 40 | -inf | 48.33 |\n", "The following table shows the constraints: \n", "| | Constraint | Right Hand Side | Shadow Price | Slack | Min RHS | Max RHS |\n", "|---:|:-------------|------------------:|---------------:|--------:|----------:|----------:|\n", "| 0 | Operation_1 | 400 | 6.67 | 0 | 300 | 525 |\n", "| 1 | Operation_2 | 600 | 11.67 | 0 | 0 | 800 |\n", "| 2 | Operation_3 | 600 | 0 | 166.67 | 433.33 | inf |\n" ] } ], "source": [ "total_profit = pulp.value(model.objective)\n", "print(\"Total profit is %0.2f €\"%total_profit)\n", "\n", "print(\"The following table shows the decision variables: \")\n", "var_df = pd.DataFrame.from_dict(cell_units, orient=\"index\", \n", " columns = [\"Variables\"])\n", "var_df[\"Solution (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.X))\n", "var_df[\"Reduced cost (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.RC))\n", "var_df[\"Objective Coefficient (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.Obj))\n", "var_df[\"Objective Lower bound (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.SAObjLow) if item.solverVar.SAObjLow > -0.1 else \"-Inf\" )\n", "var_df[\"Objective Upper bound (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.SAObjUp) if item.solverVar.SAObjUp != item.solverVar.UB else \"Inf\")\n", "\n", "\n", "print(var_df.to_markdown())\n", "\n", "\n", "const_dict = dict(model.constraints)\n", "con_df = pd.DataFrame.from_records(list(const_dict.items()), exclude=[\"Expression\"], columns=[\"Constraint\", \"Expression\"])\n", "con_df[\"Right Hand Side\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.RHS))\n", "con_df[\"Shadow Price\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.Pi))\n", "con_df[\"Slack\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.Slack))\n", "con_df[\"Min RHS\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.SARHSLow) )\n", "con_df[\"Max RHS\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.SARHSUp) if const_dict[item].solverConstraint.SARHSUp < 1e10 else \"Inf\" )\n", "\n", "\n", "print(\"The following table shows the constraints: \")\n", "print(con_df.to_markdown())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 1\n", "Peter Weyland believes that, for the reputation of the company, Weyland should manufacture at least 40 ultra cells per month. If this plan goes ahead, how would it affect the current profit?" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "pycharm": { "is_executing": false }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "40 extra units of ultra would lower the profits: **333.333€**\n" ] } ], "source": [ "answer_1 = -40*cell_units[\"ultra\"].solverVar.RC;\n", "print(\"40 extra units of ultra would lower the profits: **%0.3f€**\"%answer_1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 2\n", "The engineer informed management that due to maintenance operations, the capacities of Operation 1, 2, and 3 have changed to 360, 600 and 500 respectively. How would this affect the profit?" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "pycharm": { "is_executing": false }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We need to check the shadow price of Operation 1 and 2. Operation 3 has a surplus of capacity and the minimum RHS is below the new capacity, so it will have no impact.\n", "The profit would be reduced in **266.80** € per month\n" ] } ], "source": [ "print(\"We need to check the shadow price of Operation 1 and 2. Operation 3 has a surplus of capacity and the minimum RHS is below the new capacity, so it will have no impact.\")\n", "\n", "b2 = [360, 600, 500]\n", "maintenance = np.subtract(b,b2)\n", "answer_2=np.dot(maintenance, pd.to_numeric(con_df[\"Shadow Price\"]))\n", "\n", "\n", "print(\"The profit would be reduced in **%0.2f** € per month\"%answer_2)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 3\n", "Mr. Weyland insisted that the company needs to change the strategy towards producing ultra-fast cells to position Weyland Corp in this segment. The company reviewed the prices of the ultra-fast cells and changed them to 30€, 10€ and 50€ per fast, normal and ultra cells. With the new prices, would it be profitable to produce ultra-fast cells?" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "pycharm": { "is_executing": false }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We need to verify the bounds for the objective coefficients for the three variables.\n", "First we check if the new coefficients of the objective function would change the basic solution.\n", "| | Variables | Solution (GRB) | Reduced cost (GRB) | Objective Coefficient (GRB) | Objective Lower bound (GRB) | Objective Upper bound (GRB) |\n", "|:------|:------------|-----------------:|---------------------:|------------------------------:|------------------------------:|------------------------------:|\n", "| ultra | cells_ultra | 0 | -8.33 | 40 | -inf | 48.33 |\n", "It is profitable to produce ultra fast cells with the new prices\n" ] }, { "data": { "text/markdown": [ "the variables that change the basic solution are:" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "print(\"We need to verify the bounds for the objective coefficients for the three variables.\")\n", "print(\"First we check if the new coefficients of the objective function would change the basic solution.\")\n", "display(Markdown(\"the variables that change the basic solution are:\")) \n", "new_profits = [30, 10, 50]\n", "entering_df = var_df[(new_profits < pd.to_numeric(var_df[\"Objective Lower bound (GRB)\"])) | (new_profits > pd.to_numeric(var_df[\"Objective Upper bound (GRB)\"]))]\n", "print(entering_df.to_markdown())\n", "\n", "answer_3 = \"It is profitable to produce ultra fast cells with the new prices\" if (\"ultra\" in entering_df.index) else \"It is not profitable to produce ultra fast cells with the new prices\"\n", "print(answer_3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 4\n", "What is the impact in the new profit if we opted for this new prices?" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "pycharm": { "is_executing": false }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We need to define a new model (model 2) for the reviewed price.\n", "The total profit is **10000.00** € per month\n", "The profit would change in **333.33** € per month\n" ] }, { "name": "stderr", "output_type": "stream", "text": [ "c:\\python38\\lib\\site-packages\\pulp\\pulp.py:1199: UserWarning: Spaces are not permitted in the name. Converted to '_'\n", " warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n" ] } ], "source": [ "print(\"We need to define a new model (model 2) for the reviewed price.\")\n", "\n", "model2 = pulp.LpProblem(\"Updated model for Weyland Corp\", pulp.LpMaximize)\n", "# Technological Coefficients:\n", "unit_profits2 = [30, 10, 50]\n", "\n", "# Objective Function\n", "model2 += (\n", " pulp.lpSum([\n", " unit_profits2[i] * cell_units[cell_types[i]]\n", " for i in range(len(cell_types))])\n", ")\n", "\n", "#Iterate matrix raws\n", "#Since there is no change in the capacities, we can use the same constraints\n", "for i in range(len(A)):\n", " model2 += pulp.lpSum([\n", " A[i][j] * cell_units[cell_types[j]] \n", " for j in range(len(cell_types))]) <= b[i] , operations[i] \n", "\n", "#note that in this case all constraints are of type less or equal\n", "model2.solve()\n", "pulp.LpStatus[model2.status]\n", "total_profit2 = pulp.value(model2.objective)\n", "\n", "print(\"The total profit is **%.2f** € per month\"%total_profit2)\n", "\n", "answer_4 = total_profit2 - total_profit \n", "print(\"The profit would change in **%0.2f** € per month\"%answer_4)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Question 5\n", "The engineer is studying a new type of fast cells that would require 2 hours of operation 1, 0 hours of operation 2 and 1 hour of operation 3. The estimated market price is 20€. How would this affect the production plan?" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "pycharm": { "is_executing": false }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We need to define a new model (model 3) for the new standard cell type.\n", "The total profit is **10000.00** € per month\n", "The following tables show the values obtained: \n", "| | Decision Variable | Solution value | Unit profit | Reduced cost | Lower bound | Upper bound |\n", "|---:|:--------------------|-----------------:|--------------:|---------------:|--------------:|--------------:|\n", "| 0 | cells_fast | 300 | 30 | 0 | 23.3333 | inf |\n", "| 1 | cells_normal | 0 | 20 | -10 | -inf | 30 |\n", "| 2 | cells_standard | 50 | 20 | 0 | 13.3333 | 60 |\n", "| 3 | cells_ultra | 0 | 40 | -10 | -inf | 50 |\n", "[{'name': 'cells_fast', 'value': 1}, {'name': 'cells_standard', 'value': 2}, {'name': 'cells_normal', 'value': 3}, {'name': 'cells_ultra', 'value': 2}]\n", "[{'name': 'cells_fast', 'value': 2}, {'name': 'cells_ultra', 'value': 3}]\n", "[{'name': 'cells_fast', 'value': 1}, {'name': 'cells_standard', 'value': 2}, {'name': 'cells_normal', 'value': 4}]\n", "The following table shows the problem constraints: \n", "| | Constraint | Left-hand side | Direction | Right-hand side | Slack | Shadow price | Lower bound | Upper bound |\n", "|---:|:-------------|-----------------:|------------:|------------------:|--------:|---------------:|--------------:|--------------:|\n", "| 0 | Operation_1 | 400 | -1 | 400 | 0 | 10 | 300 | 600 |\n", "| 1 | Operation_2 | 600 | -1 | 600 | 0 | 10 | 0 | 800 |\n", "| 2 | Operation_3 | 400 | -1 | 600 | 200 | 0 | 400 | inf |\n", "The profit would change in **333.33** € per month\n" ] }, { "name": "stderr", "output_type": "stream", "text": [ "c:\\python38\\lib\\site-packages\\pulp\\pulp.py:1199: UserWarning: Spaces are not permitted in the name. Converted to '_'\n", " warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n" ] } ], "source": [ "print(\"We need to define a new model (model 3) for the new standard cell type.\")\n", "\n", "model3 = pulp.LpProblem(\"Updated model for Weyland Corp II\", pulp.LpMaximize)\n", "cell_types3 = ['fast', 'standard', 'normal', 'ultra']\n", "\n", "# Technological Coefficients:\n", "unit_profits3 = [30, 20, 20, 40]\n", "\n", "# New variables\n", "cell_units3 = pulp.LpVariable.dicts(\"cells\",\n", " (i for i in cell_types3),\n", " lowBound=0,\n", " cat='Continuous')\n", "# Objective Function\n", "model3 += (\n", " pulp.lpSum([\n", " unit_profits3[i] * cell_units3[cell_types3[i]]\n", " for i in range(len(cell_types3))])\n", ")\n", "#Update the constraints\n", "A=[[1, 2, 3, 2], #Coefficients of the first constraint\n", " [2, 0, 0, 3], #Coefficients of the second constraint\n", " [1, 2, 4, 0]] #Coefficients of the third constraint\n", "\n", "# Capacities\n", "b = [400, 600, 600]\n", "\n", "# Iterate matrix raws\n", "# note that in this case all constraints are of type less or equal\n", "for i in range(len(A)):\n", " model3 += pulp.lpSum([\n", " A[i][j] * cell_units3[cell_types3[j]] \n", " for j in range(len(cell_types3))]) <= b[i] , operations[i] \n", "\n", "model3.solve(solver=pulp.GUROBI(msg = 0))\n", "pulp.LpStatus[model3.status]\n", " \n", "total_profit3 = pulp.value(model3.objective)\n", "\n", "print(\"The total profit is **%.2f** € per month\"%total_profit3)\n", "\n", "# Print our decision variable values\n", "print(\"The following tables show the values obtained: \")\n", "\n", "# Now instead of using Pandas Dataframe apply, we use a for loop to create a dictionary\n", "variable_names3 = []\n", "values3 = []\n", "reduced_costs3 = []\n", "lower_bounds3 = []\n", "upper_bounds3 = []\n", "for v in model3.variables():\n", " variable_names3.append(v.name)\n", " values3.append(v.varValue)\n", " reduced_costs3.append(v.dj)\n", " lower_bounds3.append(v.solverVar.SAObjLow)\n", " upper_bounds3.append(v.solverVar.SAObjUp)\n", " \n", "variable_raw_data3 = {\"Decision Variable\": variable_names3,\n", " \"Solution value\": values3,\n", " \"Unit profit\": unit_profits3,\n", " \"Reduced cost\": reduced_costs3,\n", " \"Lower bound\": lower_bounds3,\n", " \"Upper bound\": upper_bounds3}\n", "\n", "var_df3 = pd.DataFrame(variable_raw_data3)\n", "print(var_df3.to_markdown())\n", "\n", "# Print out the values of the constraints\n", "constraint_names3 = []\n", "constants3 = []\n", "senses3 = []\n", "pis3 = []\n", "slacks3 = []\n", "shadow_prices3 = []\n", "rhs_upper_bounds3 = []\n", "rhs_lower_bounds3 = []\n", "\n", "for name, c in list(model3.constraints.items()):\n", " constraint_names3.append(name)\n", " print(c.to_dict())\n", " constants3.append(-c.constant)\n", " senses3.append(c.sense)\n", " pis3.append(c.pi)\n", " slacks3.append(c.slack)\n", " shadow_prices3.append(c.modified)\n", " rhs_lower_bounds3.append(c.solverConstraint.SARHSLow)\n", " rhs_upper_bounds3.append(c.solverConstraint.SARHSUp)\n", "\n", "print(\"The following table shows the problem constraints: \")\n", "\n", "constraint_raw_data3 = {\"Constraint\":constraint_names3,\n", " \"Left-hand side\":np.subtract(constants3,slacks3),\n", " \"Direction\":senses3,\n", " \"Right-hand side\":constants3,\n", " \"Slack\": slacks3,\n", " \"Shadow price\": pis3,\n", " \"Lower bound\": rhs_lower_bounds3,\n", " \"Upper bound\": rhs_upper_bounds3\n", " }\n", "\n", "const_df3 = pd.DataFrame(constraint_raw_data3)\n", "print(const_df3.to_markdown())\n", "\n", "answer_4 = total_profit2 - total_profit \n", "print(\"The profit would change in **%0.2f** € per month\"%answer_4)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 6\n", "Mr. Weyland thinks that the operation time for Operation 2 for the normal cells can be cut to only 3h. How would this improve the production plan?" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.1" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 1 }